﻿#include <bits/stdc++.h>
using namespace std;

// 【题目】力扣739.每日温度
// 【难度】中等
// 【提交】2024.3.24 https://leetcode.cn/problems/coin-change/submissions/515820318/
// 【标签】单调栈
// 版本二
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T)
    {
        stack<int> st;
        vector<int> result(T.size(), 0);
        for (int i = 0; i < T.size(); i++)
        {
            while (!st.empty() && T[i] > T[st.top()])
            { 
                result[st.top()] = i - st.top();
                st.pop();
            }
            st.push(i);

        }
        return result;
    }
};

//总结:
//每个元素最多入栈和出栈一次，时间复杂度为 O (n)，远优于暴力解法的 O (n²)
//对于不熟悉单调栈的开发者来说，代码逻辑可能不够直观